\part{Operating system}

\chapter{Overview}


计算机系统由硬件和软件组成，其中软件可以分为操作系统和应用程序两类，应用程序使用计算机硬件来解决用户的问题，操作系统代表用户来控制和访问硬件。

操作系统的两个主要设计目标分别是有效地使用硬件和容易地使用资源。

\begin{compactitem}
\item 操作系统是介于硬件和用户（或程序）之间的接口；
\item 操作系统是一种使得其他程序更加方便和有效运行的程序（或程序集）；
\item 操作系统管理计算机系统中每个部件的活动，并确保计算机系统中的硬件和软件能够更加有效地使用。
\item 在计算机系统出现资源使用冲突时，操作系统负责进行仲裁。
\end{compactitem}



\section{Introduction}


\subsection{UNIX}


1969年由Bell Lab的Thomson和Ritchie开发的UNIX是一个多用户、多进程（多道程序）和可移植的操作系统，并且影响了后续的BSD、Linux等操作系统。

UNIX操作系统提供了功能强大的工具（命令）来配合脚本等解决实际问题，而且操作系统本身包含了设备驱动程序，因此具有设备无关性。

UNIX操作系统本身包含多个简单、单一目的的函数，并且以系统调用的形式来提供服务，从而可以组合起来实现指定的任务，因此UNIX操作系统广泛应用于单机个人环境、分时系统和客户/服务器系统等。


UNIX的主要组成部分包括内核、命令解释器、标准工具和应用程序，系统所有其他部分均调用内核来执行相应的服务。

命令解释器（shell）是UNIX对用户的可见部分，用来接收和解释用户输入的命令，这样在接收到用户输入的命令后就可以请求内核来执行命令或运行应用程序。

\subsection{Linux}

Linux最初需要运行在UNIX系统之上，其初始内核与UNIX的子集相似，从1997年发布的Linux2.0内核开始发展成为商业操作系统，并且具备了传统UNIX的所有特性。

Linux内核负责处理所有的内核职责（例如内存管理、进程管理、设备管理和文件管理等），系统库（glibc）包含一组应用程序可以调用的函数（包括命令解释器）来与内核交互。

Linux系统工具可以使用系统库提供的服务，并执行管理任务等。

Linux支持标准因特网协议，并且支持套接字（socket）接口、协议驱动和网络设备驱动。

Linux的安全机制提供了传统UNIX定义的安全特性（例如身份验证和访问控制）。

\subsection{Windows}


Microsoft在20世纪80年代后期由David Cutler领导开发了替代MS-DOS的NT内核，并实现了可扩展性、可移植性、可靠性、兼容性和性能。

NT操作系统被设计成具有多层的面向对象的模块化体系结构，允许高层随时间而改变，不会影响底层。

内核是面向对象软件的一个片段，从而可以把任何实体都看作对象。

\begin{compactitem}
\item 硬件抽象层（HAL）为上层隐藏了硬件的差异。
\item  NT执行层由六个子系统组成，分别是对象管理器、安全引用监控器、进程管理器、虚拟内存管理器、本地过程调用工具和输入/输出管理器，从而为整个操作系统提供服务。
\item 相比运行在内核态（特权）的NT执行层，运行在用户态（无特权）的环境子系统被设计用来允许NT内核运行应用程序，其中运行为NT设计的应用的本地子系统称为Win32/64。
\end{compactitem}

NT操作系统使用的NTFS文件系统可以从文件-系统错误中恢复。










\section{Histroy}


最早的操作系统是出现于20世纪50年代的用于大型计算机（Mainframe）的批处理操作系统，需要使用穿孔卡片输入数据，使用行式打印机来输出结果，以及使用磁带作为辅助存储介质。

大型计算机中每个运行的程序称为一个作业（job），批处理操作系统只保证将计算机所有资源从一个作业转换到另一个作业。

多道程序概念的引入使得可以将多个作业同时装入内存，并且仅当资源可用时需要的作业。例如，当某个程序正在使用输入/输出设备时，CPU就处于空闲状态，并且可以供其他程序使用。

另外，多道程序引入了分时的概念来将资源让不同的作业分享，每个作业可以被分配到一个时间段来使用资源，对用户不可见的隐藏在多道程序背后的分时系统使得大型机的每个用户都感觉整个计算机在为自己服务。


使用分时技术的多道程序极大地提高了计算机的效率，不过它们需要一个可以提供调度功能的更加复杂的操作系统，从而可以决定不同的进程（即程序）在不同的时刻可以使用的资源。

\begin{compactitem}
\item 一个作业是一个要运行的程序；
\item 一个进程是在内存中等待分配资源的程序。
\end{compactitem}

用户对更快和更有效的需求催生了并行系统，这样可以在同一计算机中使用多个CPU，每个CPU可以处理一个程序或程序的一部分，这样就可以使用并行方式来进行多任务处理。

计算机网络的产生使得可以使用分布在世界各地的计算机来完成计算的不同部分，这样资源可以是分布式的，而且分布式系统结合了以往系统的特点和新的功能（例如安全控制）。

与通用操作系统同时发展的实时（Real-time）操作系统可以在特定时间限制内完成任务，从而可以使运行其上的实时应用程序可以监控、响应或控制外部过程或环境，而且实时应用程序可以作为嵌入式系统（Embedded）运行在特定的系统中。

实时操作系统的需求通常和通用操作系统的需求是不同的。

\begin{compactitem}
\item 实时系统可以用作交通控制、临床监控或军事控制系统等；
\item 嵌入式系统可以用于汽车的控制系统以及通讯系统等。
\end{compactitem}

\section{Booting}


操作系统本身也是软件，也需要被装入内存来运行，因此它需要通过自举（booting）过程来把自己载入内存。

为了实现操作系统自举，在BIOS中存储自举加载程序，这样当计算机被加电时，CPU计数器被设置为自举程序的第一条指令，并执行程序中的指令。

自举程序唯一的职责就是把操作系统本身（需要启动计算机的部分）载入内存，这样就结束了操作系统自举的第一阶段。

在计算机完成载入操作系统的初始部分后，CPU计数器被设置为内存中操作系统的第一条指令，从而开始执行操作系统启动和运行。



\section{Kernel}


现代操作系统内核至少包含内存管理、进程调度、硬件管理和文件管理四种功能。


\subsection{Memory Management}


内存分配必须由操作系统进行管理以避免“内存溢出”错误，例如在单道程序中的大多数内存用于装载完整的单一的程序（这里考虑数据作为程序的一个部分被程序处理），少数内存用来装载操作系统，并且在运行结束后载入新的程序来取代原来的程序。

在多道程序下，同一时刻可以载入多个程序并且能够同时被执行，CPU轮流为它们服务，而且多道程序从20世纪60年代开始经过了一系列的改进。

\begin{compactitem}
\item 使用非交换技术的程序在运行期间始终驻留在内存中。


\item 使用交换技术的程序在运行过程中可以在内存和硬盘之间进行多次数据交换。

\end{compactitem}

分区调度技术将内存划分为不定长的多个分区，每个部分或分区保存一个程序，CPU在多个程序之间交替服务。

CPU从一个程序开始，执行一些指令，直到有输入/输出操作或者分配给程序的时限到达，然后CPU保存最近使用的指令所在的内存地址后转入下一个程序。

在CPU轮询中，对每个程序都采用同样的步骤反复执行，当所有的程序执行结束后，再转回第一个程序，而且CPU可以使用优先级管理来控制分配给每个程序的CPU时间。

在分区调度技术下，每个程序都完全载入内存，并占用连续的地址，不过在提高CPU的使用效率的同时也存在如下问题：

\begin{compactitem}
\item 分区的大小必须由内存管理器预先决定。
\item 在紧缩分区并删除空闲区和创建新分区时都将增加额外的系统开销。
\end{compactitem}

分页调度技术把内存分成大小相等的若干个部分（称为帧），程序则被分为大小相等的部分（称为页）。

通常情况下，帧和页的大小一样，并且与系统用于从存储设备中提取信息的块的大小相等，从而提高分区调度的效率。

页被载入内存中的帧，这样程序在内存中就不必是连续的，多个连续的页可以占用内存中不连续的帧，从而在一定程度上提高了效率，不过整个程序仍然需要在运行前全部载入内存。

请求分页调度取消了分页调度的限制，程序仍然被划分为页，每个页可以依次载入内存和运行，然后被另一个页代替。

\begin{compactitem}
\item 内存可以同时载入多个程序的页；
\item 来自同一个程序的连续页可以不必载入同一个帧；
\item 一个页可以被载入任何一个空闲帧
\end{compactitem}

分段调度类似于分段调度，而且可以将程序划分为段，每个段依次被载入内存中等待执行，然后被来自同一个程序或其他程序的模块所代替。

请求分页和分段调度结合了两者的优点来提高系统效率，太大的段（即模块）无法载入内存中的空闲区时就可以划分为页来依次载入内存中的帧中等待被处理。


请求分页和请求分段调度意味着当程序运行时可能一部分程序驻留在内存中，其他部分则位于硬盘上，因此引入了虚拟内存来支持请求分页调度、请求分段调度，或者同时支持。


\subsection{Process Management}

在现代操作系统中，对程序、作业和进程进行了明确的定义。

\begin{compactitem}
\item 程序是硬盘等存储设备上的一组稳定的指令，操作系统来决定程序是否会成为作业。
\item 作业是操作系统选中某个程序并开始执行，直到其运行结束并再次成为一个程序的过程。
\item 进程是处于执行状态的程序，而且还未结束，因此进程可以理解为在内存中运行的作业。
\end{compactitem}

程序、作业和进程各自具有不同的状态，例如进程可以处于运行状态或者等待就绪状态等。

\begin{compactitem}
\item 每个作业都是程序，但是并不是所有的程序都是作业。
\item 每个进程都是作业，但是作业未必是进程。
\end{compactitem}

事实上，计算机系统运行时会有许多的作业和进程相互竞争计算资源，状态图可以用来显示每个实体（作业或进程）的不同状态。例如，当某些作业进入内存时，其他的作业就必须等待直到有可用空间，或者当一个进程正在使用CPU时，其他进程就必须等待直到CPU空闲为止。


\begin{compactitem}
\item 程序被操作系统选中时就成为作业并且进入保持（或等待）状态，直到它进入内存之前都将维持保持状态。
\item 内存可以整体或部分地载入程序时就将作业转换到就绪状态，并变成进程，直到它进入CPU并执行。
\item 进程进入CPU就转换为执行状态，直到执行完毕退出CPU，或执行中断返回到就绪状态。
\end{compactitem}

当进程处于运行状态后，可能出现如下三种情况之一。

\begin{compactitem}
\item 进程运行直至它需要I/O资源，进程进入等待状态，直至I/O结束。
\item 进程可能耗尽所分配的时间片，进程直接进入就绪状态。
\item 进程终止，进程进入终止状态。
\end{compactitem}

如果操作系统使用虚拟内存，并且需要在内存中将程序载入或退出，那么状态图可能更加复杂。

进程管理器使用调度器和队列来管理进程。例如，为了将一个作业或进程从一个状态改变为另一个状态，进程管理器使用了两个调度器（作业调度器和进程调度器）。


\begin{compactitem}
\item 作业调度器将一个作业从保持状态转入就绪状态，或是从运行状态转入终止状态。换句话说，作业调度器负责从作业中创建一个进程和终止一个进程。
\item 进程调度器将一个进程从一个状态转入另一个状态。例如，当一个进程等待某一事件发生来使其从运行状态转入就绪状态。
\end{compactitem}


当一个进程所分配的时间片用完时，该进程将从运行状态转入就绪状态，接着当CPU准备执行该进程时，进程调度器又会让该进程从就绪状态转入运行状态。


另外，操作系统还可以使用其他类型的调度器来使进程之间的转换更为有效。


为了处理多个进程和作业，进程管理器使用队列（等待列表）来管理进程，与作业或进程相关的时保存作业和进程相关信息的作业控制块或进程控制块（PCB）。

进程管理器在队列中存储的不是作业或进程，而是作业或进程控制块，作业或进程太大而无法被复制到队列中，因此它们仍保存在内存或硬盘中，作业控制块或进程控制块就是等待中的作业和进程的代表。

操作系统中维护着多个不同种类的队列（例如作业队列、就绪队列和I/O队列）。例如，可能有多个I/O队列，而且每一个对应一个I/O设备。

\begin{compactitem}
\item 作业队列用来保存等待内存的作业；
\item 就绪队列用来保存已经在内存中准备就绪正在等待CPU的进程；
\item I/O队列用来保存正在等待I/O设备的进程。
\end{compactitem}

进程管理器可以使用多种策略从队列中选择下一个作业或进程，可以是先入先出（FIFO）、最短长度优先或最高优先级等。


所有的进程管理器的思想都是使得拥有不同资源的不同进程同步，这样就可以使资源被多个用户（或进程）同时使用，不过进程就可能面临两种有问题的状态：死锁和饿死。

大多数操作系统中的文件都是不可共享的，当一个文件被某个进程使用时将不能再被其他的进程使用，因此如果操作系统没有对进程的资源进行限制时，就会发生死锁（dead lock）。


假设有两个进程A和B，进程A已经占有了文件File1（即File1已经分配给了A），而且进程A只有得到另一个文件File2（进程A已经请求了File2）才能够释放File1。与此同时，File2已经被进程B占有了（即File2分配给了进程B），而且进程B只有得到文件File1才能（进程B已经请求了File1）释放文件File2，这种情况下就发生了进程死锁。

\begin{quote}
\texttt{死锁是指一个进程由于其他进程无限制地使用资源导致无法运行的情况。}
\end{quote}


现实情况中的窄桥与死锁类似，资源（桥的一端）被一辆车占用，该车只有到达桥的另一端才能释放资源，但是同时桥的另一端正被另一辆车占用，反过来情况也一样。

死锁发生在操作系统允许一个进程运行，而不首先检查它所必需的资源是否准备好，是否允许该进程占有资源直到它不需要为止。

死锁的发生需要如下四个必要条件：

\begin{compactenum}
\item 互斥：一个资源只能被一个进程占有；
\item 资源：一个进程占有一个资源，而且在占有其他资源前无法使用该资源；
\item 抢先：操作系统不能林时对资源重新分配；
\item 循环等待：所有的进程和资源包含在一个循环里。
\end{compactenum}

上述四个条件都是死锁发生所必需的，但是它们只是必要条件（不是充分条件），因此对于死锁来说它们必须同时出现，但是它们不一定能引起死锁。也就是说，只要上述四个条件中的一个没有出现，死锁就不会发生，从而给用户提供了一种防止或避免死锁的方法。


\begin{compactitem}
\item 当所需资源不空闲时，不允许请求进程运行。
\item 限制进程占用资源的时间，否则强制退出。
\end{compactitem}

饿死是一种与死锁相反的情况，当操作系统对进程分配资源有太多限制时就可能发生饿死。例如，假如一个操作系统中规定一个进程只有在所需的所有资源都为其占有时才能执行时就可能发生进程饿死。

假设进程A需要文件File1和File2，但是File1正被进程B使用，File2正被进程C使用。进程B将首先终止并释放File1，但是File2一直不被释放，因此进程A就一直不能执行。与此同时，进程D只需要File1就可以执行，因此被释放的File1就会被进程D占有，就算进程C终止并释放File2，但是File1已经被另外的进程占有，因此进程A仍然不能执行，从而发生饿死。

\begin{quote}
\texttt{饿死是指一个进程由于资源分配限制太多而不能执行的情况的情况。}
\end{quote}

\subsection{Device Management}

设备管理器（或者是输入/输出管理器）负责访问输入/输出设备来有效地管理数据。

在计算机系统中，输入/输出设备相比CPU和内存在数量和速度上都存在速度限制，因此当一个进程访问访问输入/输出设备时，对于其他进程就是不可用的。

\begin{compactitem}
\item 设备管理器监视所有的输入/输出设备以保证它们能够正常运行，并且可以在为一个进程结束服务后继续为下一个进程服务。
\item 设备管理器为所有的输入/输出设备维护一个队列，或者为类似的输入/输出设备维护一个或多个队列。例如，当设备管理器在管理多个打印机时可以分别用一个队列维护一个设备，或者用一个队列维护两个设备。
\item 设备管理器控制用于访问输入/输出设备的不同策略。例如，可以使用先入先出策略来维护一个设备，并且使用最短长度优先策略来维护另一个设备。
\end{compactitem}

\subsection{Filesystem Management}

文件管理器可以控制对文件的访问，只有获得访问权限的应用程序才能访问文件，而且访问类型可以不同。

\begin{quote}
\texttt{只有进程或用户被允许访问指定文件时，访问才被允许。}
\end{quote}


另外，文件管理器可以管理文件的创建、存储、归档、辈分、删除、修改和重命名等。




\section{User Interface}


操作系统中的用户界面或命令解释程序负责接收用户（进程）的输入并向操作系统翻译请求，从而操作系统可以与外界通信，

\begin{compactitem}
\item 命令解释程序（shell）用于UNIX/Linux等操作系统中。
\item 菜单驱动的图形用户界面用于Windows等操作系统中。
\end{compactitem}




























































































